package main

import "math"

func getMin(vals []int) int {
	min := math.MaxInt32
	for _, v := range vals {
		if v < min {
			min = v
		}
	}
	return min
}

func coinChange(coins []int, amount int) int {
	if coins == nil || len(coins) == 0 {
		return -1
	}
	if amount == 0 {
		return 0
	}
	t := make([]int, amount+1)
	t[0] = 0
	for i := 1; i <= amount; i++ {
		options := make([]int, 0)
		for _, v := range coins {
			j := i - v
			if j >= 0 && t[j] != -1 {
				options = append(options, t[j])
			}
		}
		if len(options) == 0 {
			t[i] = -1
		} else {
			t[i] = getMin(options) + 1
		}
	}
	return t[amount]
}

func main() {
	println(coinChange([]int{1, 2, 5}, 11))
}
